home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / XPtrList.cpp < prev    next >
C/C++ Source or Header  |  1999-07-13  |  5KB  |  273 lines
  1. #include "XPtrList.h"
  2. #include "nodeClass.h"
  3.  
  4.  
  5. void* XPtrList::sDummy = NULL;
  6.  
  7.  
  8. XPtrList::XPtrList( ListOrderingT inOrdering ) {
  9.  
  10.     mOrdering    = inOrdering;
  11.     mCompFcn    = NULL;
  12. }
  13.  
  14.  
  15.  
  16.  
  17. void XPtrList::Assign( const XPtrList& inList ) {
  18.  
  19.     UtilStr::Assign( inList );
  20. }
  21.  
  22.  
  23.  
  24. #define __ptr( idx )    *((void**) (base + idx * 4))
  25.  
  26. long XPtrList::FetchPredIndex( const void* inPtr ) const {
  27.     long M, L = 0, R = Count()-1;
  28.     char* base = getCStr();
  29.     long order = ( mOrdering == cSortHighToLow ) ? 0x80000000 : 0;
  30.  
  31.     if ( R < 0 ) 
  32.         return 0;
  33.     else {
  34.         while (L <= R) {
  35.             
  36.             M = (L + R) / 2;
  37.             
  38.             if ( (mCompFcn( inPtr, __ptr( M ) ) ^ order) >= 0 ) // If inPtr <= __ptr( M )...
  39.                 R = M - 1;                                        // Throw away right half
  40.             else
  41.                 L = M + 1;                                        // Throw away left half
  42.         }
  43.  
  44.         if ( L > R )                                            // Catch the case where R+1==L
  45.             L = M;                                                // In this case, M specifies the critical element 
  46.             
  47.         // At this point, we know L is the critical element (case: L==R or L contains M from case above)
  48.         if ( mCompFcn( inPtr, __ptr( L ) ) < 0 )                // If inPtr > __ptr( M )...
  49.             L++;
  50.  
  51.         return L;
  52.     }
  53. }
  54.  
  55.  
  56. void XPtrList::SetCompFcn( CompFunctionT inFcn, bool inSortLowToHigh ) {
  57.     mCompFcn = inFcn;
  58.     
  59.     RemoveAll();
  60.     
  61.     if ( inSortLowToHigh )
  62.         mOrdering = cSortLowToHigh;
  63.     else
  64.         mOrdering = cSortHighToLow;
  65.  
  66. }
  67.  
  68.  
  69.  
  70. long XPtrList::FindIndexOf( const void* inMatch ) const {    
  71.     long    i = 0;
  72.     char*    curPtr, *endPtr;
  73.     void*    ptr;
  74.  
  75.     if ( mCompFcn ) {
  76.         i = FetchPredIndex( inMatch );
  77.         curPtr = getCStr() + 4 * i;
  78.         endPtr = getCStr() + length();
  79.         while ( curPtr < endPtr ) {
  80.             i++;
  81.             ptr = *((void**) curPtr);
  82.             if ( ptr == inMatch )
  83.                 return i;
  84.                 
  85.             // Stop checking when we hit items that aren't equal to inMatch
  86.             else if ( mCompFcn( inMatch, ptr ) != 0 )
  87.                 break;
  88.             curPtr += 4;
  89.         } }
  90.     else {
  91.         curPtr = getCStr();
  92.         endPtr = curPtr + length();
  93.  
  94.         while ( curPtr < endPtr ) {
  95.             i++;
  96.             if ( *((void**) curPtr) == inMatch ) 
  97.                 return i;
  98.             else
  99.                 curPtr += 4;
  100.         }
  101.     }
  102.  
  103.     return 0;
  104. }
  105.  
  106.  
  107.  
  108.  
  109. long XPtrList::Add( const void* inPtrToAdd ) {
  110.     long i;
  111.     
  112.     if ( mCompFcn ) {
  113.         i = FetchPredIndex( inPtrToAdd );
  114.         Insert( i*4, (char*) &inPtrToAdd, 4 ); 
  115.         return i+1; }
  116.     else {
  117.         UtilStr::Append( (char*) &inPtrToAdd, 4 );
  118.         return Count();
  119.     }
  120. }
  121.  
  122.  
  123.  
  124.  
  125.  
  126. void XPtrList::Add( const void* inPtrToAdd, long inN ) {
  127.     
  128.     if ( inN < 0 )
  129.         inN = 0;
  130.         
  131.     if ( inN > Count() )
  132.         inN = Count();
  133.     
  134.     Insert( inN * 4, (char*) &inPtrToAdd, 4 );
  135. }
  136.  
  137.  
  138.  
  139.  
  140. void XPtrList::Add( const XPtrList& inList ) {
  141.  
  142.     if ( mOrdering == cOrderNotImportant )
  143.         UtilStr::Append( inList );
  144.     else {
  145.         int i, n = inList.Count();
  146.         for ( i = 1; i <= n; i++ ) 
  147.             Add( inList.Fetch( i ) );
  148.     }
  149. }
  150.  
  151.  
  152.  
  153.  
  154. void*& XPtrList::operator[] ( const long inIndex ) {
  155.     long len;
  156.     
  157.     if ( inIndex >= 0 ) {
  158.         len = mStrLen;
  159.         if ( inIndex >= len >> 2 ) {
  160.             Insert( len, '\0', ( inIndex + 1 ) * 4 - len );
  161.         }
  162.             
  163.         return *( (void**) ( mBuf + inIndex * 4 + 1 ) ); }
  164.     else
  165.         return sDummy;
  166. }
  167.             
  168.  
  169.  
  170.  
  171.  
  172. bool XPtrList::Remove( const void* inMatchPtr ) {
  173.     long    idx = FindIndexOf( inMatchPtr );
  174.     
  175.     return RemoveElement( idx );
  176. }
  177.  
  178.  
  179.  
  180. bool XPtrList::RemoveElement( long inIndex ) {
  181.     char* s;
  182.     
  183.     if ( inIndex > 0 && inIndex <= Count() ) {
  184.         inIndex--;
  185.         if ( mOrdering == cOrderNotImportant ) {
  186.             s = getCStr();
  187.             *( (void**) (s + inIndex * 4) ) = *( (void**) (s + length() - 4 ) );
  188.             Trunc( 4 ); }
  189.         else 
  190.             UtilStr::Remove( inIndex * 4 + 1, 4 );
  191.         return true; }
  192.     else
  193.         return false;
  194. }
  195.  
  196.  
  197.  
  198.  
  199. bool XPtrList::RemoveLast() {
  200.  
  201.     if ( length() > 0 ) {
  202.         Trunc( 4 );
  203.         return true; }
  204.     else
  205.         return false;
  206. }
  207.  
  208.  
  209. void XPtrList::RemoveAll() {
  210.     Wipe();
  211. }
  212.  
  213.  
  214.  
  215.  
  216. void XPtrList::MoveToHead( long inIndex ) {
  217.     void* p;
  218.     char* s;
  219.     
  220.     if ( inIndex > 1 ) {
  221.         if ( Fetch( inIndex, &p ) ) {
  222.             inIndex--;
  223.             s = getCStr();
  224.             if ( mOrdering == cOrderNotImportant )
  225.                 *( (void**) (s + inIndex * 4) ) = *( (void**) s);    
  226.             else
  227.                 UtilStr::Move( s+4, s, inIndex * 4 );
  228.             *( (void**) s) = p;
  229.         }
  230.     }
  231. }
  232.  
  233.  
  234.  
  235.  
  236. void* XPtrList::Fetch( long inIndex ) const {
  237.     if ( inIndex >= 1 && inIndex <= length() >> 2 )
  238.         return *( (void**) (getCStr() + ( inIndex - 1 ) * 4) );
  239.     else
  240.         return NULL;
  241. }
  242.  
  243.  
  244. bool XPtrList::Fetch( long inIndex, void** ioPtrDest ) const {
  245.     
  246.     if ( ioPtrDest ) {
  247.         if ( inIndex >= 1 && inIndex <= length() / 4 ) {
  248.             *ioPtrDest = *( (void**) (getCStr() + ( inIndex - 1 ) * 4) );
  249.             return true; }
  250.         else
  251.             *ioPtrDest = NULL;
  252.     }
  253.     
  254.     return false;
  255. }
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263. void XPtrList::Randomize() {
  264.     void*    temp, **ptrArray = (void**) getCStr();
  265.     long    i, randIdx, n = Count();
  266.     
  267.     for ( i = 0; i < n; i++ ) {
  268.         randIdx = nodeClass::Rnd( 1, n );
  269.         temp = ptrArray[ i ];
  270.         ptrArray[ i ] = ptrArray[ randIdx-1 ];
  271.         ptrArray[ randIdx-1 ] = temp; 
  272.     }
  273. }